import java.util.*;

/**
 * 99. 恢复二叉搜索树
 * https://leetcode-cn.com/problems/recover-binary-search-tree/
 */
public class Solutions_99 {
    public static void main(String[] args) {
        String str1 = "[1 3 # # 2]";  // output: {3, 1, null, null, 2}
        TreeNode treeNode1 = MyTreeNodeUtils.deserialize(str1);

        String str2 = "[3 1 4 # # 2]";  // output: {2, 1, 4, null, null, 3}
        TreeNode treeNode2 = MyTreeNodeUtils.deserialize(str2);

        List<TreeNode> inputs = new ArrayList<>();
        inputs.add(treeNode1);
        inputs.add(treeNode2);

        for (TreeNode input : inputs) {
            recoverTree(input);
            System.out.println(MyTreeNodeUtils.serialize(input));
        }
    }

    /**
     * 解题思路：通过中序遍历的方式，找到两个顺序错误的节点
     * 若 root 中序遍历后，得到数组 {3, 2, 1}
     * 则 3 和 1 是顺序错乱的节点
     * 中序遍历时，当前元素与前一元素比较，若当前元素小于前一元素，则两个节点的顺序是错误的
     * 注意点：2 小于 3，先记录下 error1 = 3, error2 = 2
     * 而后面遍历到 1 时，发现 1 又小于 2，则需要更新 error2 为 1（error1 不做改变）
     *
     * 而数组 {1, 3, 2, 4} 中，2 小于 3，同样记录下 error1 = 3, error2 = 2
     * 而该数组中只有一处当前元素小于前一元素的情况，所以最终 error1 就是 3，error2 就是 2
     */
    public static void recoverTree(TreeNode root) {
        // 栈方式实现中序遍历
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        // 记录两个错误的节点的值，方便进行交换
        TreeNode error1 = null, error2 = null;
        // 记录中序遍历时的前一元素
        TreeNode last = null;

        while (!stack.isEmpty() || cur != null) {
            // 依次存储左子节点
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 取出父节点
            TreeNode temp = stack.pop();
            if (last != null && temp.val < last.val) {
                // 两个节点的顺序错误
                if (error1 == null) {
                    error1 = last;
                }
                error2 = temp;
            }
            last = temp;
            // 遍历父节点的右子节点
            cur = temp.right;
        }
        // 交换两个错误节点的值
        int temp = error1.val;
        error1.val = error2.val;
        error2.val = temp;
    }
}
